###########################################
# PERCEPTRON
###########################################
# Perceptron algorithm
# Parameters:
#          Y: the truth labels
#          X: the feature vectors
#          kernel: a function that takes two vectors u, v and returns
#                  the kernel of u and v
# Returns: a vector M_ind of booleans that indicates the indices of the mistake points
#          if M_ind[j] = TRUE, then j is a mistake point
#          if M_ind[j] = FALSE,  then j is not a mistake point
perceptron <- function(Y, X, kernel){
  # a stack of features of the mistake points
  # Its rows form a subset of the rows of X
  M_x <- matrix(numeric(0), 0, dim(X)[2])
  
  # a stack of labels of the mistake points
  # (defined as a matrix with only one column)
  M_Y <- matrix(numeric(0), 0, 1)
  
  # a vector of booleans that indicates the indices of the mistake points
  M_ind <- rep(FALSE, dim(X)[1])
  
  for (t in 1:dim(X)[1]){
    # a vector pre_kern whose dimension is equal to size of the current mistake set
    #
    # The sum of all the components of pre_kern represents the number k(w^t, x^t)
    # where w^t is the current weight vector (not computed explicitly)
    # The j-th component of pre_kern is equal to y^j * \phi(x^j) \cdot \phi(x^t)
    # where x^t = the t-th row of X  
#     print("M_Y")
#     print(M_Y)
#     print("M_x")
#     print(M_x)
#     print("X[t,]")
#     print(X[t,])    
    if (length(M_Y) > 1){
      pre_kern = M_Y * apply(M_x, 1, kernel, v=X[t,])
    } else {
      pre_kern = M_Y * kernel(M_x, X[t,])
    }
#     print("sum(pre_kern)")
#     print(sum(pre_kern))
    # prediction
    y_hat = ifelse(sum(pre_kern) >= 0, 1, -1)
#     print("y_hat")
#     print(y_hat)
#     print("t")
#     print(t)
#     print("Y[t]")
#     print(Y[t])
    
    if (y_hat != Y[t]){
      #print("made a mistake :(")
      #print(paste("expected label was", Y[t]))
      #print(paste("perceptron output label was", y_hat))
      # memorizing this mistake by adding this data point
      # to the mistake set
      M_x = as.matrix(rbind(M_x, X[t,]))
      M_Y = as.matrix(rbind(M_Y, Y[t]))
      M_ind[t] = TRUE     
    }
  }
  #print("perceptron: all original labels of mistake pts")
  #print(Y[M_ind])
  return (M_ind)
}

###########################################
# KERNELS
###########################################
# alternative version of polynomial kernel
getPolyKernel <- function(deg){
  function(u,v){
    (sum(u * v) + 1) ^ deg
  }
}

# a polynomial kernel that returns the dot product of the vectors 
# in a feature space of all polynomials of degree up to a specified degree
# Parameters: u, v: two vectors with the same dimensions
#              deg: the degree of the kernel
# Returns: (u \cdot v + 1)^d
poly_kernel.deg <- function(u, v){
  return ((sum(u * v) + 1) ^ deg)
}

# an exponential kernel
# Parameters: u, v: two vectors with the same dimensions
#                window: the window-size of the kernel
# Returns: exp(-||u-v||/2s^2), where s = window-size
exp_kernel.window <- function(u,v){
  # the 2-norm distance between u and v
  distance = norm(as.matrix(u - v), "2")
  
  return (exp(-distance / (2 * window^2)))
}
